import java.util.HashMap;
import java.util.Map;

public class O35 {
    Map<Node,Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head==null)
            return null;
        if (!map.containsKey(head)){
            Node node = new Node(head.val);
            map.put(head,node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
        return map.get(head);
    }
//    public void dfs(Node node){
//        if (node==null)
//            return;
//        if (!map.containsKey(node)){
//
//        }
//
//    }
}
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
